package com.arithmetic.basics;

/**
 * 给你一棵二叉树的根节点，返回该树的 直径 。
 * 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
 * 两节点之间路径的 长度 由它们之间边数表示。
 * 示例 1：
 * 输入：root = [1,2,3,4,5]
 * 输出：3
 * 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
 * 示例 2：
 * <p>
 * 输入：root = [1,2]
 * 输出：1
 * 提示：
 * <p>
 * 树中节点数目在范围 [1, 104] 内
 * -100 <= Node.val <= 100
 * Related Topics
 * 树
 * 深度优先搜索
 * 二叉树
 */
public class Day33 {
    /**
     * 解题思路
     * 实质是最大长度，实质等于求左右子树的最大长度：
     * (1)root==0，长度为0
     * (2)求左右子树的长度（递归）
     * (3)左右子树中的最大长度+1即为最大长度
     */
    int max = 0;

    public int diameterOfBinaryTree(Day28.TreeNode root) {
        getRootLength(root);
        return max;
    }

    // 单子树的最大长度
    public int getRootLength(Day28.TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 左子树的最大长度
        int left = getRootLength(root.left);
        // 右子树的最大长度
        int right = getRootLength(root.right);
        if (left + right > max) {
            max = left + right;
        }
        return 1 + Math.max(left, right);
    }
}
